package top.minuy.structure.graph.matching;

import top.minuy.structure.graph.bipartition.dfs.BipartitionDetection;
import top.minuy.structure.graph.network.MaxFlowDynamic;
import top.minuy.structure.graph.representations.table.Graph;
import top.minuy.structure.graph.representations.table.WeightedGraphDynamic;

/**
 * 最大流二分图匹配
 *
 * @author Minuy
 * @time 20:59
 * @date 2021/11/29
 */
public class BipartiteMatching {
    private Graph g;
    private int s, t;
    private int maxMatching;

    public BipartiteMatching(Graph g) {
        this.g = g;

        if (g.isDirected()) {
            throw new IllegalArgumentException("BipartiteMatching only works in undirected graph.");
        }

        BipartitionDetection bd = new BipartitionDetection(g);
        if (!bd.isBipartition()) {
            throw new IllegalArgumentException("BipartiteMatching only works for bipartite graph.");
        }

        // 创建最大流网络
        WeightedGraphDynamic wgd = createNetWork(bd);

        // 计算最大匹配
        MaxFlowDynamic mfd = new MaxFlowDynamic(wgd, s, t);
        maxMatching = mfd.maxFlow();
    }

    private WeightedGraphDynamic createNetWork(BipartitionDetection bd) {
        WeightedGraphDynamic wgd = new WeightedGraphDynamic(true);

        // 添加顶点
        for (int v = 0; v < g.V(); v++) {
            wgd.addVertex(v);
        }
        s = g.V();
        t = s + 1;
        wgd.addVertex(s);
        wgd.addVertex(t);

        // 蓝 -> 绿
        for (int v = 0; v < g.V(); v++) {
            if (bd.isBlue(v)) {
                wgd.addEdge(s, v, 1);
            } else {
                wgd.addEdge(v, t, 1);
            }
            for (int w : g.adj(v)) {
                if (w < v) { // 不存在等于w==v的情况，这样可以过滤掉一般的无向图“边”
                    // 下面的可能会产生平行边问题
                    /* if (bd.isBlue(v) && (!bd.isBlue(w))) { // 蓝->绿
                        wgd.addEdge(v, w, 1);
                        wgd.addEdge(s, v, 1);
                        wgd.addEdge(w, t, 1);
                    } else if (bd.isBlue(w) && (!bd.isBlue(v))) { // 蓝->绿
                        wgd.addEdge(w, v, 1);
                        wgd.addEdge(s, w, 1);
                        wgd.addEdge(v, t, 1);
                    }*/
                    if (bd.isBlue(v)) {
                        wgd.addEdge(v, w, 1);
                    } else {
                        wgd.addEdge(w, v, 1);
                    }
                }
            }
        }

        return wgd;
    }

    /**
     * 获取最大匹配
     *
     * @return int 最大匹配
     * @author Minuy
     * @date 2021/11/29 21:37
     */
    public int maxMatching() {
        return maxMatching;
    }

    /**
     * 查看是否是完全匹配
     *
     * @return boolean 是否是完全匹配
     * @author Minuy
     * @date 2021/11/29 21:38
     */
    public boolean isPerfectMatching() {
        return maxMatching * 2 == g.V();
    }
}
